/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
typedef struct TreeNode TreeNode;  // 定义树节点类型别名，简化后续使用

int count;  // 用于记录节点总数的全局变量

// step 1# 先序遍历二叉树，统计节点数量
void preOrder(TreeNode *root) {
    if (root == NULL) return;  // 若当前节点为空，直接返回
    count++;                   // 当前节点不为空，节点数加一
    preOrder(root->left);      // 递归遍历左子树
    preOrder(root->right);     // 递归遍历右子树
}

// step 2# 统计整棵树的节点数量
int countNodes(struct TreeNode* root) {
    count = 0;           // 初始化节点计数器
    preOrder(root);      // 调用先序遍历函数统计节点
    return count;        // 返回节点总数
}


// 迭代法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
const int MAX = 100000;  // 栈最大容量，假设最多处理10万个节点

typedef struct TreeNode TreeNode;  // 简化结构体名的使用

// step 1# 定义栈结构体：用于实现遍历时的节点存储
typedef struct {
    TreeNode **data;  // 指向节点指针的数组
    int top;          // 栈顶索引
    int capacity;     // 栈容量
} Stack;

// step 2# 创建一个指定容量的栈
Stack *creatStack(int capacity) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));                       // 分配栈结构体空间
    stack->data = (TreeNode **)malloc(sizeof(TreeNode) * capacity);     // 分配存储数据的数组
    stack->top = -1;                                                     // 初始化栈顶
    stack->capacity = capacity;
    return stack;
}

// step 3# 判断栈是否为空
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

// step 4# 将一个节点压入栈中
void push(Stack *stack, TreeNode *node) {
    if ((stack->top)+1 == stack->capacity) return;  // 防止栈溢出
    stack->data[++(stack->top)] = node;             // 栈顶前移并存入节点
}

// step 5# 弹出栈顶节点
TreeNode *pop(Stack *stack) {
    if (stack->top == -1) return NULL;         // 若栈为空，返回NULL
    return stack->data[(stack->top)--];        // 返回栈顶节点并下移栈顶
}

// step 6# 释放栈所占用的内存
void freeStack(Stack *stack) {
    free(stack->data);
    free(stack);
}

// step 7# 使用栈进行前序遍历，统计所有节点的数量（非递归）
int countNodes(struct TreeNode* root) {
    if (root == NULL) return 0;                   // 空树直接返回0
    int count = 0;                                // 节点计数器初始化
    Stack *stack = creatStack(MAX);               // 创建栈，用于辅助遍历
    push(stack, root);                            // 将根节点压栈

    while (!isEmpty(stack)) {                     // 当栈不为空时持续遍历
        TreeNode *curNode = pop(stack);           // 弹出栈顶节点
        count++;                                   // 节点数加一
        if (curNode->left != NULL)                // 若左子树存在，压入栈中
            push(stack, curNode->left);
        if (curNode->right != NULL)               // 若右子树存在，压入栈中
            push(stack, curNode->right);
    }

    freeStack(stack);                             // 遍历完成后释放栈内存
    return count;                                 // 返回节点总数
}
